class CountInversePairs:
    count = 0

    def merge_and_sort(self, left_nums, right_nums):
        left, right = 0, 0
        len_left, len_right = len(left_nums), len(right_nums)
        res = []

        while left < len_left and right < len_right:
            if left_nums[left] > right_nums[right]:
                res.append(right_nums[right])
                right += 1
                self.count += len(left_nums[left:])
            else:
                res.append(left_nums[left])
                left += 1

        if left <= len_left:
            res += left_nums[left:]
        if right <= len_right:
            res += right_nums[right:]
        return res

    def sort(self, nums):
        if len(nums) <= 1:
            return nums
        mid = len(nums) // 2
        left_nums, right_nums = nums[:mid], nums[mid:]
        res = self.merge_and_sort(self.sort(left_nums), self.sort(right_nums))
        return res


if __name__ == "__main__":
    nums = [4, 2, 3, 1]
    count_inverse_pairs = CountInversePairs()
    count_inverse_pairs.sort(nums)
    print(count_inverse_pairs.count)